# O(nlogn)
# class Solution(object):
#     def wiggleSort(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: None Do not return anything, modify nums in-place instead.
#         """
#         nums.sort()
#         for i in range(1, len(nums) - 1, 2):
#             temp = nums[i]
#             nums[i] = nums[i + 1]
#             nums[i + 1] = temp
#         return nums

class Solution(object):
    def wiggleSort(self, nums):
        for i in range(0, len(nums) - 1, 2):
            if nums[i + 1] < nums[i]:
                temp = nums[i]
                nums[i] = nums[i + 1]
                nums[i + 1] = temp
            if i > 0:
                if nums[i] > nums[i - 1]:
                    temp = nums[i]
                    nums[i] = nums[i - 1]
                    nums[i - 1] = temp
        if len(nums) >= 3 and len(nums) % 2 == 1:
            if nums[-1] > nums[-2]:
                temp = nums[-1]
                nums[-1] = nums[-2]
                nums[-2] = temp
        return nums


data = Solution()
nums = [1, 2, 3]
print(data.wiggleSort(nums))
nums = [3, 5, 2, 1, 6, 4]
print(data.wiggleSort(nums))
